【题解】 [Vani有约会]雨天的尾巴 线段树+启发式合并 luoguP4556 | Qiuly's blog!

【题解】 [Vani有约会]雨天的尾巴 线段树+启发式合并 luoguP4556

Posted on | In | Comments:

毒瘤出题人，卡时间卡空间！

嗯，如果这一题不是在树上的话貌似可以直接权值线段树维护？不过到了树上的话难道可以权值线段树+树链剖分，表示不明白。于是尝试了一发线段树合并，但是我们的线段树是权值线段树。

我们的权值线段树是用来存原树中 $x$ 结点以及其子树中的每种救济粮的个数。

怎么个合并法呢，其实特别简单，两个线段树同时进行，发现到了一个节点的时候一个线段树有这个结点另一个没有这个节点，那么这个节点以及其下面的结点的信息都可以直接作为新线段树的这个节点的信息。

当然如果到了一个叶子节点，直接将两个线段树的这个位置的救济粮的个数加起来即可。

嗯，每个线段树再维护一个值存出现最多次数的救济粮是什么，这样就可以得到答案了。但是为了避免一些结点与其子树压根就没有救济粮的情况，我们需要判断一下这个节点与其子树是否有救济粮即可。

然后直接一遍 $dfs$ ，遍历 $u$ 的所有孩子然后拿 $u$ 的线段树依次去和 $u$ 的儿子的线段树合并。最终合并完的线段树存储的就是 $u$ 以及其子树的信息了。然后就可以获得答案了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+7;
const int LogN=27;
const int M=6e6+7;

int n,m,q,X[N],Y[N],Z[N],Ans[N],head[N],cnt;
struct Edge {int nxt,to;}G[N<<1];

inline void add(int u,int v) {
    G[++cnt]=(Edge){head[u],v},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u},head[v]=cnt;
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=--x;
}

namespace Lca {
    int dep[N],fa[N][LogN+4];
    void dfs(int u,int f) {
        fa[u][0]=f,dep[u]=dep[f]+1;
        for(int i=1;i<=LogN;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
        for(int i=head[u];i;i=G[i].nxt)
            if(G[i].to!=f) dfs(G[i].to,u);
    }
    int lca(int x,int y) {
        if(x==y)return x;
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=LogN;i>=0;--i)
            if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
        if(x==y)return x;
        for(int i=LogN;i>=0;--i)
            if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
}using namespace Lca;

struct Segment_Tree {
    #define mid ((l+r)>>1)
    int rt[N],lc[M],rc[M],d[M],t[M],tot;
    void pushup(int x) {
        if(d[lc[x]]>=d[rc[x]]) d[x]=d[lc[x]],t[x]=t[lc[x]];
        else d[x]=d[rc[x]],t[x]=t[rc[x]];
    }
    int update(int x,int l,int r,int pos,int val) {
        if(!x) x=++tot;
        if(l==r) {d[x]+=val;t[x]=l;return x;}
        if(pos<=mid) lc[x]=update(lc[x],l,mid,pos,val);
        else rc[x]=update(rc[x],mid+1,r,pos,val);
        pushup(x);return x;
    }
    int merge(int x,int y,int l,int r) {
        if(!x) return y;
        if(!y) return x;
        if(l==r) {d[x]+=d[y];t[x]=l;return x;}
        lc[x]=merge(lc[x],lc[y],l,mid);
        rc[x]=merge(rc[x],rc[y],mid+1,r);
        pushup(x);return x;
    }
}T;

void calc(int u,int f) {
    for(int i=head[u];i;i=G[i].nxt)
        if(G[i].to!=f) 
            calc(G[i].to,u),
            T.rt[u]=T.merge(T.rt[u],T.rt[G[i].to],1,m);
    if(T.d[T.rt[u]]) Ans[u]=T.t[T.rt[u]];
}

int main() {
    IN(n),IN(q);
    for(int i=1,x,y;i<n;++i)
        IN(x),IN(y),add(x,y);
    for(int i=1;i<=q;++i)
        IN(X[i]),IN(Y[i]),IN(Z[i]),m=max(m,Z[i]);
   	//权值线段树离线处理
    dfs(1,0);
    for(int i=1;i<=q;++i) {
        int lca_xy=lca(X[i],Y[i]);
        T.rt[X[i]]=T.update(T.rt[X[i]],1,m,Z[i],1);
        T.rt[Y[i]]=T.update(T.rt[Y[i]],1,m,Z[i],1);
        T.rt[lca_xy]=T.update(T.rt[lca_xy],1,m,Z[i],-1);
        if(fa[lca_xy][0]) T.rt[fa[lca_xy][0]]=T.update(T.rt[fa[lca_xy][0]],1,m,Z[i],-1);
    }
    calc(1,0);
    for(int i=1;i<=n;++i) printf("%d\n",Ans[i]);
    return 0;
}

本文标题:【题解】 [Vani有约会]雨天的尾巴 线段树+启发式合并 luoguP4556

文章作者:Qiuly

发布时间:2019年04月02日 - 00:00

最后更新:2019年04月02日 - 15:57

原始链接:http://qiulyblog.github.io/2019/04/02/[题解]luoguP4556/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。